package com.shuang.tree6;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class InorderTraversal {

    //方法二：迭代
    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> result = new ArrayList<Integer>();

        if (root == null) {
            return result;
        }

        //中序遍历 左中右
        //  入栈顺序： 左-右
        //拿到当前节点 如果其左指向不为空就接着往下走到左边 直到这个节点左指向为空
        // 封装这个节点结果（相当于一个中节点） 在检查这个节点右指向是否为空 不为空封装这个右指向节点的结果
        // 为空的话 退回到上一个节点（利用栈弹出将节点退回） 封装上一个节点结果 再检查上一个节点的右指向...

        //定义栈
        Stack<TreeNode> stack = new Stack<>();

        //定义一个用于指向当前节点位置的节点
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            //指向一直往左下边走 将每个节点的值存到栈中 直到走到一个节点的左指向为空 证明走到了最下面最左边的那个节点即将左边的节点都存到栈中了
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                //左边都存到栈中了 curr走到了左边最后的节点的左指向 为空

                //弹出当前节点(左边最后一个节点)（相当于一个中节点） 再给到curr
                curr = stack.pop();
                //封装结果
                result.add(curr.val);
                curr = curr.right;
            }
        }

        //循环结束 返回结果
        return result;
    }
}
